// https://leetcode.cn/problems/score-of-parentheses/
// Created by ade on 2022/10/9.
// 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
//
// () 得 1 分。
// AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
// (A) 得 2 * A 分，其中 A 是平衡括号字符串
#include <string>
#include <iostream>
#include <math.h>
#include <stack>

using namespace std;

class Solution {
public:

    // 核心思想是获取括号的深度
    int scoreOfParentheses1(string s) {
        int base = 0;
        int sum = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                base++;
            } else {
                cout << "base:" << base << endl;
                sum += pow(2, base - 1);
                base--;
                while (i + 1 < s.size() && s[i + 1] == ')' && base > 0) {
                    base--;
                    i++;
                }
                cout << "sum:" << sum << ",base:" << base << endl;
            }
        }
        return sum;
    }

    // 栈的方式解决问题 (()())()
    // 0 0 0
    // 0 1
    // 0 1 0
    // 0 2
    // 4
    // 4 0
    // 5
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);
        for (auto c : s) {
            if (c == '(') {
                st.push(0);
            } else {
                int v = st.top();
                st.pop();
                st.top() += max(2 * v, 1);
            }
        }
        return st.top();
    }
};

int main() {
    Solution so;
    string s = "(()())()";
    cout << so.scoreOfParentheses(s);
    return 0;
}